import java.util.*;

/**
* @description: 851. 喧闹和富有
* @author hewei
* @date 2022/9/8 20:27
* @version 1.0
*/

public class LoudAndRich {

    public int[] loudAndRich1(int[][] richer, int[] quiet) {
        int n = quiet.length;
        List<Integer>[] edge = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            edge[i] = new ArrayList<>();
        }
        for (int[] rich : richer) {
            edge[rich[1]].add(rich[0]);
        }
        int[] ans = new int[n];
        Arrays.fill(ans, -1);
        for (int i = 0; i < n; i++) {
            dfs(i, quiet, edge, ans);
        }
        return ans;
    }

    public void dfs(int x, int[] quite, List<Integer>[] edge, int[] ans) {
        if (ans[x] != -1) return;

        ans[x] = x;
        for (Integer i : edge[x]) {
            dfs(i, quite, edge, ans);
            if (quite[ans[i]] < quite[ans[x]]) ans[x] = ans[i];
        }
    }

    public int[] loudAndRich(int[][] richer, int[] quiet) {
        int n = quiet.length;
        int[] inEdge = new int[n];
        List<Integer>[] edge = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            edge[i] = new ArrayList<>();
        }
        for (int[] rich : richer) {
            edge[rich[0]].add(rich[1]);
            inEdge[rich[1]]++;
        }
        int[] ans = new int[n];
        for (int i = 0; i < n; i++) {
            ans[i] = i;
        }
        Deque<Integer> queue = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (inEdge[i] == 0) queue.add(i);
        }
        while (!queue.isEmpty()) {
            Integer index = queue.poll();
            for (Integer i : edge[index]) {
                if (quiet[ans[i]] > quiet[ans[index]]) ans[i] = ans[index];
                inEdge[i]--;
                if (inEdge[i] == 0) queue.add(i);
            }
        }
        return ans;
    }
}
